package com.uhu.code;

/**
 * 240. 搜索二维矩阵 II
 * https://leetcode.cn/problems/search-a-2d-matrix-ii/?envType=study-plan-v2&envId=top-100-liked
 */
public class Solution240 {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        int n = matrix[0].length;
        int maxI = m - 1;
        int maxJ = n - 1;
        for(int j = 0; j < n; j++) {
            if(matrix[0][j] == target) {
                return true;
            }
            if(matrix[0][j] > target) {
                maxJ = j - 1;
            }
        }
        for(int i = 0; i < m; i++) {
            if(matrix[i][0] == target) {
                return true;
            }
            if(matrix[i][0] > target) {
                maxI = i - 1;
            }
        }
        for(int i = 0; i <= maxI; i++) {
            for(int j = 0; j <= maxJ; j++){
                if(matrix[i][j] == target) {
                    return true;
                }
            }
        }
        return false;
    }
}
